package common

const INF = 0x3f3f3f3f

// Reverse 字符串反转
func Reverse(s string) string {
	n := len(s)
	b := []byte(s)
	i, j := 0, n-1
	for i < j {
		b[i], b[j] = b[j], b[i]
		i++
		j--
	}
	return string(b)
}

// Min 求最小值
func Min(nums ...int) int {
	// 32位整型最大小值
	result := nums[0]
	for _, num := range nums {
		if result > num {
			result = num
		}
	}
	return result
}

// Max 求最大值
func Max(nums ...int) int {
	result := nums[0]
	for _, num := range nums {
		if result < num {
			result = num
		}
	}
	return result
}

// MaxInt64 求最大值
func MaxInt64(nums ...int64) int64 {
	result := nums[0]
	for _, num := range nums {
		if result < num {
			result = num
		}
	}
	return result
}

// 求总和
func Sum(nums ...int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}
	ans := 0
	for _, v := range nums {
		ans += v
	}
	return ans
}

// GCD 最大公约数, x y不能为0
func GCD(a, b int) int {
	if b > a {
		a, b = b, a
	}
	if a%b == 0 {
		return b
	}
	return GCD(a%b, b)
}

// 二叉树
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// N叉树
type Node struct {
	Val      int
	Children []*Node
}

// 链表
type ListNode struct {
	Val  int
	Next *ListNode
}

type Heap struct {
	Arr       []int
	IsMaxHeap bool
}

// 计算序列长度
func (h Heap) Len() int {
	return len(h.Arr)
}

// h.Arr[i] < h.Arr[j]表示小根堆，h.Arr[i] > h.Arr[j]表示大根堆
func (h Heap) Less(i, j int) bool {
	if !h.IsMaxHeap {
		// 使表达式为true的i所对应元素排前面，j所对应元素排后面；否则i所对应元素排后，j所对应元素排前
		return h.Arr[i] < h.Arr[j]
	} else {
		return h.Arr[i] > h.Arr[j]
	}
}

// 交换元素
func (h Heap) Swap(i, j int) {
	h.Arr[i], h.Arr[j] = h.Arr[j], h.Arr[i]
}

// 不要直接调用h.Push和Pop方法，而是调用heap.Push()和heap.Pop()
// heap.Push()和heap.Pop()内部会调用h.Push()和h.Pop()进行元素的添加和删除
// 然后再调用up(Push)或down(Pop)对重新调整顺序
func (h *Heap) Push(x interface{}) {
	(*h).Arr = append((*h).Arr, x.(int))
}

// 删除元素
func (h *Heap) Pop() interface{} {
	n := len(h.Arr) - 1
	x := h.Arr[n]
	h.Arr = h.Arr[:n]
	return x
}
